#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.

"""

dp formula
dp[m][n] = max(
    dp[m][n-1],
    dp[m-1][n],
    1 + dp[m-1][n-1]        # if A[m] == B[n]
)

"""


class Solution:
    def longestCommonSubsequence(self, A, B):
        # 不必连续
        if not A or not B:
            return 0

        len_a = len(A)
        len_b = len(B)

        self.record = self.make_matrix(len_a+1, len_b+1, -1)

        return self.longest_of_index_rec(A, len_a, B, len_b)

    def longest_of_index_rec(self, A, idx_a, B, idx_b):
        # 递归可以在字符串相同时, 避免矩阵中相邻操作.
        if idx_a == 0 or idx_b == 0:
            return 0

        v = self.record[idx_a][idx_b]
        if v != -1:
            return v

        if A[idx_a-1] == B[idx_b-1]:
            value = 1 + self.longest_of_index_rec(A, idx_a-1, B, idx_b-1)
        else:
            value = max(self.longest_of_index_rec(A, idx_a-1, B, idx_b), self.longest_of_index_rec(A, idx_a, B, idx_b-1) )

        self.record[idx_a][idx_b] = value
        return value


    def make_matrix(self, rows, cols, init_v=None):
        one_row = [init_v] * cols
        matrix = [list(one_row) for i in range(rows)]
        return matrix


def main():
    print("start main")
    s = Solution()
    ret = s.longestCommonSubsequence("daabeddbcedeabcbcbec", "daceeaeeaabbabbacedd")
    print(ret)

if __name__ == "__main__":
    main()
